#include<iostream>

using namespace std;

template<class T>
class MyHeap
{
public:
    /* data */
    T * array;
    int CurrentSize;

    MyHeap(/* args */int lenght);
    ~MyHeap();
    void BuildHeap();
    bool isLeaf(int pos) const
    {
        if(2*pos+1>=MaxSize)
        {
            return true;
        }
        else return false;
    }
    int leftchild(int pos) const
    {
        return 2*pos+1;
    }
    int rightchild(int pos) const
    {
        return 2*pos+2;
    }
    int parent(int pos) const
    {
        if(pos!=0)
        return (pos-1)/2;
        else exit(0);
    }
    bool Remove(int pos)
    {
        int swaptemp;
        swaptemp = array[pos];
        array[pos] = array[CurrentSize-1];
        array[CurrentSize-1] = array[pos];
        CurrentSize--;
        SiftUp(CurrentSize);

    }
    void SiftUp(int position);
    void printHeap()
    {
        for(int i = 0;i<CurrentSize;i++)
        {
            cout<<i<<":"<<array[i]<<" ";
        }
        cout<<endl;
    }
    void InsertNode(T item)
    {
        if(CurrentSize==MaxSize) exit(0);
        else
        {
            CurrentSize++;
            array[CurrentSize-1] = item;
            
        }
        
    }

};
template<class T>
MyHeap<T>::MyHeap(/* args */int length)
{
    array = new T[length];
    MaxSize = length;
    CurrentSize = 0;
}
template<class T>
MyHeap<T>::~MyHeap()
{
    delete[] array;
}
template<class T>
void MyHeap<T>::SiftUp(int position)
{
    int pos = 0;
    
    pos = leftchild(pos);
    for(int i = 0;!isLeaf(i)&&i<position+1;i++)
     pos = i;
     cout<<"pos"<<pos<<endl;
     
    while(pos>=0)
    {
        int temp = pos;
    int ptemp = temp;
    int swaptemp;
        
        while(leftchild(temp)<MaxSize)
        {
            //getchar();
            cout<<leftchild(temp)<<endl;
            if(array[leftchild(temp)]>array[temp]||(rightchild(temp)<MaxSize&&array[rightchild(temp)]>array[temp]))
            {
                cout<<"temp: "<<temp<<endl;
                
                if(rightchild(temp)>=MaxSize)
                {
                
                    ptemp = leftchild(temp);
                
                }
                else if(array[rightchild(pos)]>array[leftchild(pos)])
                {
                    ptemp = rightchild(temp);
                }
                else ptemp = leftchild(temp);
                swaptemp = array[temp];
                array[temp] = array[ptemp];
                array[ptemp] = swaptemp;
                
                cout<<"swap between "<<temp<<" "<<ptemp<<endl;
                temp = ptemp;
            }
            else break;
           // if(ptemp == temp) cout<<"STOP！"<<endl;
            
        }
        pos--;
        //cout<<"pos--"<<endl;
    }
    
    
}
